// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"strconv"
)

type Vertex struct {
	// key是顶点的唯一标识
	Key int
	// Vertices 将描述连接到这个的顶点
	// 键将是连接顶点的键值
	// 值是指向它的指针
	Vertices map[int]*Vertex
}

// 初始化顶点
func NewVertex(key int) *Vertex {
	return &Vertex{
		Key:      key,
		Vertices: map[int]*Vertex{},
	}
}

func (v *Vertex) String() string {
	s := strconv.Itoa(v.Key) + ":"

	for _, neighbor := range v.Vertices {
		s += " " + strconv.Itoa(neighbor.Key)
	}

	return s
}

type Graph struct {
	// Vertices 描述图中包含的所有顶点
	Vertices map[int]*Vertex
	// 这将决定它是有向图还是无向图
	directed bool
}

// 初始化有向图
func NewDirectedGraph() *Graph {
	return &Graph{
		Vertices: map[int]*Vertex{},
		directed: true,
	}
}

// 初始化无向图
func NewUndirectedGraph() *Graph {
	return &Graph{
		Vertices: map[int]*Vertex{},
	}
}

// 添加顶点
func (g *Graph) AddVertex(key int) {
	v := NewVertex(key)
	g.Vertices[key] = v
}

// 添加边方法
func (g *Graph) AddEdge(k1, k2 int) {
	v1 := g.Vertices[k1]
	v2 := g.Vertices[k2]

	// 如果其中一个顶点不存在，则返回错误
	if v1 == nil || v2 == nil {
		return
	}

	// 如果顶点已经连接，则什么也不做
	if _, ok := v1.Vertices[v2.Key]; ok {
		return
	}

	v1.Vertices[v2.Key] = v2
	if !g.directed && v1.Key != v2.Key {
		v2.Vertices[v1.Key] = v1
	}

	// 将顶点添加到图的顶点图中
	g.Vertices[v1.Key] = v1
	g.Vertices[v2.Key] = v2
}

func (g *Graph) String() string {
	s := ""
	i := 0
	for _, v := range g.Vertices {
		if i != 0 {
			s += "\n"
		}
		fmt.Println(v.Key)
		s += v.String()
		i++
	}
	return s
}

func DFS(g *Graph, startVertex *Vertex) {
	// 维护一个已访问节点的映射以防止访问相同的节点
	visited := map[int]bool{}

	if startVertex == nil {
		return
	}
	visited[startVertex.Key] = true

	// 对于每个相邻的顶点，递归调用该函数
	for _, v := range startVertex.Vertices {
		if visited[v.Key] {
			continue
		}
		DFS(g, v)
	}
}

func main() {
	graph := NewDirectedGraph()
	graph.AddEdge(0, 1)
	graph.AddEdge(0, 2)
	graph.AddEdge(1, 2)
	graph.AddEdge(2, 3)
	vertex := NewVertex(2)
	graph.Vertices = map[int]*Vertex{2: vertex}
	DFS(graph, vertex)
	graph.String()
}

//$ go run dfs.go
//2
